package org.nlp.algo.sort;
 
 import java.util.*;
 /**
  * 堆(Heap)
  * @author Kemaswill
  * 2012-10-5 Friday
  */
 
 public class Heap {
     
     public static int[] data;
     public static int length;
     public static int heap_size;
     
     public Heap(){
         this.length=20;
         this.heap_size=length;
         this.data=new int[length];
         Random random=new Random(System.currentTimeMillis());
         for(int i=0;i<length;i++){
             data[i]=Math.abs(random.nextInt()%50);
         }//for
     }
     
     public Heap(int n){
         this.length=n;
         this.heap_size=length;
         this.data=new int[length];
         Random random=new Random(System.currentTimeMillis());
         for(int i=0;i<length;i++){
             data[i]=Math.abs(random.nextInt()%50);
         }//for
     }
     
     public static void max_heapify(Heap heap,int i){
         if(i<heap.heap_size){
             int l=2*i+1;
             int r=2*i+2;
             int target=i;
             if(l<heap.heap_size&&heap.data[l]>heap.data[i]){
                 target=l;
             }
             if(r<heap.heap_size&&heap.data[r]>heap.data[target]){
                 target=r;
             }
             if(target!=i){
                 exchange(heap,i,target);
                 max_heapify(heap,target);
             }//if
         }//if        
     }//heapify
     
     public static void exchange(Heap heap,int x,int y){
         int tmp=heap.data[x];
         heap.data[x]=heap.data[y];
         heap.data[y]=tmp;
     }
     
     public static void build_heap(Heap heap){
         //对于所有非叶结点，依次调用max_heapify
         for(int i=heap.heap_size/2;i>=0;i--){
             max_heapify(heap,i);
         }
     }
     
     public static void heapsort(Heap heap){
         
         for(int i=heap.length-1;i>0;i--){
             exchange(heap,0,i);
             heap.heap_size--;
             max_heapify(heap,0);
         }
     }//heapsotr
     
     public static void show_heap(Heap heap){
         for(int i=0;i<=(int)Math.log(heap.length)/Math.log(2)+2;i++){
             for(int j=(int)Math.pow(2, i)-1;j<Math.pow(2, i+1)-1;j++){
                 if(j<heap.length){
                     System.out.print(heap.data[j]+" ");
                 }
                 else break;
                 }
             System.out.println();
             }        
     }
     
     public static void main(String[] args){
         Heap heap=new Heap();
         show_heap(heap);
         build_heap(heap);
         show_heap(heap);
         heapsort(heap);
         show_heap(heap);
         
     }//main
 
 }